package com.lsa.cormen.ch24.samples;

import java.io.IOException;
import java.util.Iterator;

import com.lsa.helpers.IConverter;
import com.lsa.helpers.graph.IEdgeNode;
import com.lsa.helpers.graph.IGraph;
import com.lsa.helpers.graph.TgfGraphFactory;

public class BellmandFord {
    public static void main(String[] args) throws IOException {
        final IGraph<VData, EData> g = TgfGraphFactory.readGraphFromFile("data/samples/cormen/ch24/shortest/bellman_ford/input.tgf", new IConverter<String, VData>() {
            @Override
            public VData convert(String data) {
                return new VData();
            }
        }, new IConverter<String, EData>() {
            @Override
            public EData convert(String data) {
                return new EData(Integer.valueOf(data));
            }
            }, 
            true
        );
        
        for (int i = 0; i < g.nodeCount(); i++) {
            g.nodeAttr(i).v = i;
        }
        
        g.nodeAttr(0).d = 0;
        
        for (int i = 0; i < g.nodeCount() - 1; i++) {
            Iterator<IEdgeNode<EData>> iter = g.edgeIterator();
            while(iter.hasNext()) {
                IEdgeNode<EData> e = iter.next();
                
                VData attrFrom = g.nodeAttr(e.from());
                VData attrTo = g.nodeAttr(e.to());
                if (attrTo.d > attrFrom.d + e.getData().w) {
                    attrTo.d = attrFrom.d + e.getData().w;
                    attrTo.pred = e.from();
                }
            }
        }
        
        boolean isHasCycles = false;
        Iterator<IEdgeNode<EData>> iter = g.edgeIterator();
        while(iter.hasNext()) {
            IEdgeNode<EData> e = iter.next();
            
            VData attrFrom = g.nodeAttr(e.from());
            VData attrTo = g.nodeAttr(e.to());
            if (attrTo.d > attrFrom.d + e.getData().w) {
                isHasCycles = true;
                break;
            }
        }
        if (isHasCycles) {
            System.out.println("Cycles");
        }
        else {
            VData vdata;
            int u = 15;
            while(true) {
                vdata = g.nodeAttr(u);
                if (vdata.pred != -1) {
                    EData edata = g.edgeAttr(vdata.pred, u);
                    edata.label = edata.label + " ***";
                }
                else{
                    break;
                }
                u = vdata.pred;
            }
            System.out.println("No cycles");
        }
        
        TgfGraphFactory.saveGraphAsTgf(g, new IConverter<VData, String>() {
            @Override
            public String convert(VData data) {
                return ""+data.v + " "+data.pred;
            }
        }, new IConverter<EData, String>() {

            @Override
            public String convert(EData data) {
                return ""+data.label;
            }
        }, "data/samples/small_tmp_w.tgf");
    }
    
    private static class VData {
        int pred = -1;
        int v;
        
        int d = Integer.MAX_VALUE / 2 - 1; // distance
        
        private VData() {
        }
    }
    
    private static class EData {
        int w;
        String label ="";
        
        public EData(int w) {
            this.w = w;
            label = label + w;
        }
    }
}
